package main

import "fmt"
//两个升序链表的合并 时间复杂度 O(m+n)
type ListNode struct {
	value int
	Next *ListNode
}

func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode{
	//设置一个虚拟头节点
	dummyHead := &ListNode{}
	p := dummyHead
	for list1 != nil && list2 != nil{
		if list1.value > list2.value{
			p.Next = list2
			list2 = list2.Next
		}else{
			p.Next = list1
			list1 = list1.Next
		}
		p = p.Next
	}
	if list1 != nil{
		p.Next = list1
	}
	if list2 != nil{
		p.Next = list2
	}
	return dummyHead.Next

}

func main(){


	l23 := ListNode{
		value: 4,
		Next: nil,

	}
	l22 := ListNode{
		value: 2,
		Next: &l23,

	}
	l21 := ListNode{
		value: 1,
		Next: &l22,

	}

	l13 := ListNode{
		value: 4,
		Next: nil,

	}
	l12 := ListNode{
		value: 3,
		Next: &l13,

	}
	l11 := ListNode{
		value: 1,
		Next: &l12,

	}
	L := mergeTwoLists(&l11, &l21)
	for L != nil{
		fmt.Printf("%d->",L.value)
		L = L.Next
	}
}